package zijie;

import java.util.Arrays;

public class Trap_42_2 {

    public static void main(String[] args) {
        int[] height = {5,4,1,2};
        int trap = trap(height);
        System.out.println(trap);
    }

    public static int trap(int[] height){
        int n = height.length;
        int sum = 0;
        int max = 0;
        for(int i = 0; i < n; i++){
            sum += height[i];
            if(max < height[i]){
                max = height[i];
            }
        }
        int full = max * n;

        int lmax = 0;
        int lsum = 0;
        for(int i = 0; i < n; i++){
            if(lmax < height[i]){
                lmax = height[i];
            }
            lsum += lmax;
        }

        int rmax = 0;
        int rsum = 0;
        for(int i = n-1; i >= 0; i--){
            if(rmax < height[i]){
                rmax = height[i];
            }
            rsum += rmax;
        }
        return lsum + rsum - full - sum;
    }
    public int trap2(int[] height){
        int n  = height.length;
        int sum = 0;
        int max = 0;
        for (int i = 0; i < n; i++) {
            int cur = height[i];
            sum += cur;
            max = Math.max(cur,max);
        }
        int full = max * n;
        int suml = 0;
        int maxl = 0;
        for (int i = 0; i < n; i++) {
            int cur = height[i];
            maxl = Math.max(cur,maxl);
            suml += maxl;
        }

        int sumr = 0;
        int maxr = 0;
        for (int i = n-1; i >= 0; i--) {
            int cur = height[i];
            maxr = Math.max(cur,maxr);
            sumr += maxr;
        }

        return suml+ sumr - full - sum;

    }

}
